<!DOCTYPE html>
<html lang="zh">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<meta http-equiv="X-UA-Compatible" content="ie=edge">
	<title>Document</title>
</head>
<body>
	<script>
		/**
		 *  链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。
		 *  每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成
		 *  对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。
		 *  然而，链表需要使用指针，因此实现链表时需要额外注意。
		 *  数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，
		 *  需要从起点（表头）开始迭代列表直到找到所需的元素
		 **/
		class Node{ //Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针
			constructor(element) {
			  this.element = element;
				this.next = null;
			}
		} 
		class LinkedList{
			constructor() {
			  this.length = 0;
				this.head = null;  // 存储第一个节点的引用
			}
			append(element){  // 向列表尾部添加一个新的项
				let node = new Node(element),
						current;
				if(this.head === null){  // 列表中第一个节点
					this.head = node;
				}else{
					current = this.head;  //要向列表的尾部添加一个元素，首先需要找到最后一个元素。记住，我们只有第一个元素的引用
					while(current.next){ // 循环列表，直到找到最后一项  需要一个指向列表中current项的变量
						current = current.next;
					}
					//找到最后一项，将其next赋为node，建立链接
					current.next = node; // 
				}
				this.length++; // 更新列表的长度
			}
			insert(position, element){  // 向列表的特定位置插入一个新的项
				if(position>=0 && position <= this.length){  // 检查越界值
					let node = new Node(element),
							current = this.head,
							previous,
							index = 0;
					if(position === 0){  // 在第一个位置添加
						node.next = current;
						this.head = node;
					}else{
						while(index++ < position){  // 需要循环访问列表， 找到目标位置
							previous = current;
							current = current.next;
						}
						node.next = current;  // 新项（node）和当前项链接起来
						previous.next = node;  // 改变previous和current之间的链接。需要让previous.next指向node
					}
					this.length++;
					return true;
				}else{
					return false;
				}
			}
			removeAt(position){  // 从列表的特定位置移除一项
				//检查越界值
				if (position > -1 && position < this.length){ // 验证这个位置是有效的
					var current = this.head, // 创建一个对列表中第一个元素的引用
							previous, // {3}
							index = 0; // {4}
					//移除第一项
					if (position === 0){ // 把head 赋为current.next，就会移除第一个元素
						this.head = current.next;
					} else {
						while (index++ < position){ // 需要依靠一个细节来迭代列表，直到到达目标位置
							previous = current;    // 对当前元素的前一个元素的引用
							current = current.next; // current变量总是为对所循环列表的当前元素的引用
						}
						//将previous与current的下一项链接起来：跳过current，从而移除它 
						previous.next = current.next;
					}
					this.length--;
					return current.element;
				} else {
					return null;
				}
			}
			remove(element){  // 从列表中移除一项
				let index = this.indexOf(element);
				return this.removeAt(index);
			}
			indexOf(element){  // 返回元素在列表中的索引。如果列表中没有该元素则返回-1
				let current = this.head,
						index = -1;
				while(current){
					if(element === current.element){
						return index;
					}
					index++;
					current = current.next; // 如果列表为空，或是到达列表的尾部（current = current.next将是null）
				}
				return -1;
			}
			isEmpty(){  // 如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
				return this.length === 0;
			}
			size(){  // 返回链表包含的元素个数。与数组的length属性类似
				return this.length;
			} 
			toString(){  // 由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值
				let current = this.head,  // 把current 变量当作索引
						string = '';  // 初始化用于拼接元素值的变量
				while(current){  // 循环访问列表中的每个元素
					string += current.element + (current.next ? 'n' : '');
					current = current.next;
				}
				return string;
			}
			print(){
				console.log(this.toString());
			}
		}
	</script>
</body>
</html>